Zkouška Töpfer 27.1.2025

Hodnocení:

Budou zadány 3 úlohy, celkem ohodnocené 30 body.

• 25 - 30 bodů : výborně

• 20 - 24 bodů : velmi dobře

• 15 - 19 bodů : dobře

• jinak : neúspěch

Čas: 2h 15 min

Uloha 1

(10 bodů) Hledání bezprostředního následníka v setříděném seznamu

Na vstupu obdržíme:

• Vzestupně setříděný (Pythonovský) seznam ( a ) celých čísel, v němž se čísla mohou libovolně opakovat.

• Celé číslo ( x ).

V seznamu ( a ) určete:

1. Číslo ( y ), které je bezprostředním následníkem čísla ( x ) (tj. nejmenší prvek seznamu, který je větší než ( x )).

2. Počet výskytů tohoto čísla v seznamu.

Pokud se takový bezprostřední následník v seznamu nevyskytuje, vraťte místo něj hodnotu None.
Pozor na to, že číslo ( x ) v seznamu ležet nemusí!

Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou a prostorovou složitostí (měřeno nejhorším případem) vzhledem k délce vstupního pole.

(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte prosím žádné netriviální datové struktury (jako jsou např. datové typy dictionary či set v jazyce Python), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.

(b) Zdůvodněte správnost algoritmu

(c) Odvoďte časovou a prostorovou složitost (v nejhorším případě).

Příklady vstupů a výstupů

Vstup 1:

a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
x = 10

Výstup 1:

20 3

Vstup 2:

a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
x = -50

Výstup 2:

-22 1

Vstup 3:

a = [-22, -8, -5, 0, 1, 2, 7, 20, 20, 20, 100, 200, 200]
x = 200

Výstup 3:

None

Úloha 2

(10 bodů) Maximální počet operátorů v podvýrazu bez dělení

Je zadán strom aritmetického výrazu, tj. binární strom, v jehož vnitřních vrcholech jsou uloženy operátory (+, -, *, /) a v listech čísla. Navrhněte efektivní algoritmus, který vrátí maximální počet operátorů v podvýrazu, který neobsahuje dělení (tj. neobsahuje operátor /).

Připomeňme, že podvýraz je vždy reprezentován podstromem, který obsahuje všechny následníky svého kořene.

(a) Implementace

• Svoje řešení zapište jako funkci v Pythonu.

• Využijte k tomu definici třídy pro vrchol binárního stromu.

• Použijte hlavičku funkce uvedenou níže.

• Váš kód opatřete komentáři.

• Můžete předpokládat, že vstup je zadán korektně.

(b) Zdůvodnění správnosti

• Vysvětlete, proč algoritmus správně počítá maximální počet operátorů v podvýrazu bez dělení.

(c) Analýza časové složitosti

• Odvoďte časovou složitost algoritmu jako funkci počtu vrcholů ( n ) ve stromu.

• Použijte metodu nejhoršího případu.

Definice třídy pro vrchol binárního stromu:

class VrcholBinStromu:
    """Třída pro reprezentaci vrcholu binárního stromu""" 
    def __init__(self, hodnota=None, levy=None, pravy=None):
        self.hodnota = hodnota   # Hodnoty (operátory či operandy) uložené ve vrcholech
        self.levy    = levy      # Levé dítě 
        self.pravy   = pravy     # Pravé dítě

def pocetOp(koren: VrcholBinStromu) -> int:
    """
    koren : kořen zadaného binárního stromu
    vrátí : maximální počet operátorů v podvýrazu bez dělení
    """

Příklad vstupu a výstupu

Vstup:
'↘↖ Výstup:

3

Zdůvodnění:
Podstrom zakořeněný v pravém dítěti kořene obsahuje celkem 3 operátory a všechny jsou různé od /. Naopak žádný podvýraz bez dělení s alespoň 4 operátory neexistuje.

Úloha 3

Odpovězte na následující otázky a své odpovědi vždy zdůvodněte.

(a) (5 bodů) Asymptotická analýza funkcí

Dokážte nebo vyvraťte každé z následujících tvrzení:

(a1)
Pro libovolné tři funkce $f,g,h:\mathbb{N}\to {\mathbb{R}}^{+}$ platí:

Jestliže $f=O(h)$ a $g=\Omega (h)$, potom $f=O(g)$.

(a2)
Pro libovolné tři funkce $f,g,h:\mathbb{N}\to {\mathbb{R}}^{+}$ platí:

Jestliže $f=O(h)$ a $g=\Omega (h)$, potom $f\cdot g=\Omega (h)$.

Svoji odpověď zdůvodněte, tj. tvrzení dokažte (pokud platí) či sestrojte protipříklad (pokud neplatí). Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.

(b) (5 bodů) QuickSort s pseudomediánem

V této úloze pracujeme s posloupnostmi prvků, které lze porovnávat a které se neopakují.
Prvek takové posloupnosti délky $n$ nazveme pseudomediánem pokud leží v uspořádané posloupnosti na k-tém místě, kde $\frac{n}{10}\le k\le \frac{9n}{10}$

Profesor Hammerstein se na přednášce otázal studentů: Kdyby se nám v algoritmu QuickSort podařilo v každém kroku vybrat v čase O(1) jako pivota pseudomedián, v jakém čase (měřeno nejhorším případem) algoritmus setřídí zadanou posloupnost délky n ?

Kdybychom v algoritmu QuickSort dokázali v každém kroku vybrat v čase ( O(1) ) pseudomedián jako pivota, v jakém čase (v nejhorším případě) by algoritmus setřídil vstupní posloupnost délky ( n )?

• John se domnívá, že algoritmus bude pracovat v čase $\Theta (n^2)$.

• Donald soudí, že časová složitost bude $\Theta (n\log n)$.

• Bill si myslí, že půjde o čas $\Theta (n)$.

Kteří studenti mají pravdu a kteří nikoliv (John - ANO / NE, Donald - ANO / NE, Bill - ANO / NE) ? Svoji odpověď zdůvodněte !

• Pozor, že v zadání máme $\Theta$ (nikoliv jen $O$), takže je nutné zdůvodnit jak horní, tak dolní odhad složitosti algoritmu.